package com.programmercarl.tree;

import java.util.*;

/**
 * https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/
 *
 * @author yulongtian
 * @create 2024-12-25 9:33
 */
public class Test20 {
    public static void main(String[] args) {

    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 针对二叉搜索树，一次遍历，不使用额外空间
     *
     * @param root
     * @return
     */
    int count = 0;
    int maxCount = 0;
    TreeNode pre;
    ArrayList<Integer> list;

    public int[] findMode(TreeNode root) {
        list = new ArrayList<>();
        inorderTraversal(root);
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    public void inorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        // 左
        inorderTraversal(root.left);
        // 中
        if (pre == null) {
            count = 1;
        } else if (pre.val == root.val) {
            count++;
        } else {
            count = 1;
        }
        if (count > maxCount) {
            maxCount = count;
            list.clear();
        }
        if (count == maxCount) {
            list.add(root.val);
        }
        pre = root;

        // 右
        inorderTraversal(root.right);

    }


    /**
     * 暴力无技巧
     */
    Map<Integer, Integer> map;

    public int[] findMode1(TreeNode root) {
        map = new HashMap<>();
        inorder(root);
        int[][] res = new int[map.size()][2];
        int i = 0;
        for (Integer key : map.keySet()) {
            res[i][0] = key;
            res[i][1] = map.get(key);
            i++;
        }
        Arrays.sort(res, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[1] - o1[1];
            }
        });
        ArrayList<Integer> list = new ArrayList<>();
        int target = res[0][1];
        for (int[] re : res) {
            if (re[1] == target) {
                list.add(re[0]);
            }
        }
        int[] arr = new int[list.size()];
        for (int j = 0; j < list.size(); j++) {
            arr[j] = list.get(j);
        }

        return arr;
    }

    public void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        map.put(root.val, map.getOrDefault(root.val, 0) + 1);
        inorder(root.right);
    }

}
